home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2E.HLP < prev    next >
Text File  |  1990-01-17  |  5KB  |  91 lines
  1.          Name: FFTR2E.ASM
  2.          Type: Assembler Macro
  3.       Version: 1.0
  4.   Last Change:  4-Feb-87
  5.  
  6.   Description: 1024 Point, Non-In-place, Complex FFT Macro
  7.  
  8.  This FFT macro performs a 1024 point complex FFT on external data
  9.  using the Radix 2, Decimation in Time, Cooley-Tukey FFT algorithm [1][2].
  10.  The Cooley-Tukey algorithm is perhaps the simplest and most widely
  11.  used form of FFT.  Here we demonstrate several programming techniques
  12.  and memory mapping strategies which take advantage of the DSP56000/1
  13.  architecture to perform very fast FFT's.  It does not use straight
  14.  line code to speed up FFT's but rather exploits the use of the
  15.  dual internal data buses and memories and the ability of the external
  16.  bus controller to perform one external (off-chip) access without
  17.  adding any wait states.
  18.  
  19.  FFTR2E starts by performing two Radix 2 passes on external data to
  20.  partition the 1024 complex points into four sets of 256 complex points
  21.  which can be processed independently.  We take advantage of the fact
  22.  that half of the FFT coefficients (twiddle factors) are zero for the
  23.  first two passes to reduce the number of operations by one half.  The
  24.  remaining coefficients are +1 and -1, allowing add and subtract
  25.  operations to replace coefficient lookup table accesses.  Because of
  26.  these facts, the output of the first pass can be kept internal to the
  27.  Data ALU and only the output of the second pass is written back to
  28.  memory.  At this point all data is still external.  Note that the coding
  29.  of the first two passes is written with only one external access per
  30.  instruction.  Assuming the FFTR2E macro is in internal program memory,
  31.  this guarantees that external data can be accessed at the same speed as
  32.  internal data.
  33.  
  34.  Each set of 256 complex points is then moved into the DSP56000/1 internal
  35.  data memories and a Radix 2 FFT is performed on-chip.  Thus the
  36.  calculation is non-in-place since the internal data memories are used as
  37.  a temporary workspace.  The first pass of each 256 point FFT reads the
  38.  external data input and writes the intermediate data into the internal
  39.  memories.  All intermediate passes work on internal data.  However, the
  40.  output data from the last pass of each 256 point FFT is written back to
  41.  the external data memories.  Thus the output of the 1024 point complex
  42.  FFT overwrites the input data in external data memory.
  43.  
  44.  The implementation uses 24 bit fixed point data storage and 24 bit
  45.  fixed point FFT coefficients (sine and cosine lookup tables).  The
  46.  Data ALU maintains 56 bit accumulator precision whenever possible.
  47.  All data is complex, with the real part in X Data memory and the
  48.  imaginary part in Y Data memory.  The external data buffer requires
  49.  1024 X Data and 1024 Y Data memory locations.  The algorithm is
  50.  performed "non-in-place", since the internal DSP56000/1 Data RAM's
  51.  are used as additional workspace storage. The input data is assumed
  52.  to be in normal (time-sequential) order and the output is in bit-reversed
  53.  order.  By using the reverse-carry address modifier and a separate
  54.  output data buffer, the output data may be easily unscrambled.  Other
  55.  methods also exist to unscramble the output data without a separate
  56.  output data buffer.  For maximum speed, the FFT macro performs a lookup
  57.  table operation to get new FFT coefficients (called twiddle factors) for
  58.  each group of butterflies.  The FFTR2E macro uses "twiddle factor"
  59.  lookup tables (-cosine in X memory and -sine in Y memory) stored in
  60.  external data memory.  A SINCOS macro is available to generate these
  61.  tables.  The -sine table requires 512 X Data locations and the -cosine
  62.  table requires 512 Y Data locations.
  63.  
  64.  All register initialization is performed by this macro.  However, the
  65.  macro assumes that registers which should not be altered by the FFT
  66.  have already been saved by the main program.  This allows the user to
  67.  fit the FFT macro into his application and thus control the context
  68.  switching overhead.  No data scaling is performed and no overflow
  69.  detection is done.  Modifications to this routine could allow it to
  70.  be used with the scaling modes and thus allow dynamic scaling for
  71.  each FFT pass.
  72.  
  73.  The FFTR2E macro requires 104 words of program memory.  Using a
  74.  20.5 MHz DSP56000/1, the FFTR2E macro can perform a 1024 point
  75.  complex FFT in 3.39 milliseconds.  Additional algorithm details are
  76.  included in the source file; however, more algorithm description
  77.  would be required for complete understanding by typical users.  The
  78.  test program FFTR2ET demonstrates the calling procedure for this
  79.  macro.
  80.  
  81.  References
  82.  ----------
  83.  
  84.  [1]   Cooley, J. W., and Tukey, J. W., "An algorithm for the machine
  85.        calculation of complex Fourier series," Math. Comput., vol. 19,
  86.        pp. 297-301, April 1965.
  87.  [2]   Bergland, G. D., "A guided tour of the fast Fourier transform,"
  88.        IEEE Spectrum, vol. 6, pp. 41-52, July 1969, also in Digital
  89.        Signal Processing, edited by L. R. Rabiner and C. M. Rader,
  90.        IEEE Press, pp. 228-239, 1972.
  91.